package com.lw.leetcode.other.c;

import com.lw.test.util.Utils;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1363. 形成三的最大倍数
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/16 13:09
 */
public class LargestMultipleOfThree {


    public static void main(String[] args) {
        LargestMultipleOfThree test = new LargestMultipleOfThree();

        // "981"
//        int[] arr = {8, 1, 9};

        // "8760"
//        int[] arr = {8, 6, 7, 1, 0};

        // ""
//        int[] arr = {1};

        // "0"
//        int[] arr = {0, 0, 0, 0, 0, 0};

        // "0"
        int[] arr = Utils.getArr(10000, 0, 10);

        String s = test.largestMultipleOfThree(arr);
        System.out.println(s);

    }

    public String largestMultipleOfThree(int[] digits) {
        Arrays.sort(digits);
        int length = digits.length;
        if (digits[length - 1] == 0) {
            return "0";
        }
        int sum = 0;
        int a1 = Integer.MAX_VALUE;
        int a2 = Integer.MAX_VALUE;
        int b1 = Integer.MAX_VALUE;
        int b2 = Integer.MAX_VALUE;
        for (int digit : digits) {
            sum += digit;
            int v = digit % 3;
            if (v == 1) {
                if (digit < a1) {
                    a2 = a1;
                    a1 = digit;
                } else if (digit < a2) {
                    a2 = digit;
                }
            } else if (v == 2) {
                if (digit < b1) {
                    b2 = b1;
                    b1 = digit;
                } else if (digit < b2) {
                    b2 = digit;
                }
            }
        }
        int t1 = 10;
        int t2 = 10;
        if (sum % 3 == 1) {
            if (a1 > 9) {
                if (b1 > 9 || b2 > 9) {
                    return "";
                }
                t1 = b1;
                t2 = b2;
            } else {
                t1 = a1;
            }
        } else if (sum % 3 == 2) {
            if (b1 > 9) {
                if (a1 > 9 || a2 > 9) {
                    return "";
                }
                t1 = a1;
                t2 = a2;
            } else {
                t1 = b1;
            }
        }
        StringBuilder sb = new StringBuilder(length);
        for (int i = length - 1; i >= 0; i--) {
            int t = digits[i];
            if (t == t1) {
                t1 = 10;
            } else if (t == t2) {
                t2 = 10;
            } else {
                sb.append(t);
            }
        }
        if (sb.length() > 0 && sb.charAt(0) == '0') {
            return "0";
        }
        return sb.toString();
    }
}
